package com.leetcode.题库;

import com.leetcode.common.model.TreeNode;

/**
 * @author 覃国强
 * @date 2022-05-01 11:09
 */
public class 题库_0450_删除二叉搜索树中的节点 {

  public static void main(String[] args) {
    TreeNode node2 = new TreeNode(2);
    TreeNode node3 = new TreeNode(3);
    TreeNode node4 = new TreeNode(4);
    TreeNode node5 = new TreeNode(5);
    TreeNode node6 = new TreeNode(6);
    TreeNode node7 = new TreeNode(7);

    node3.left = node2;
    node3.right = node4;

    node6.right = node7;

    node5.left = node3;
    node5.right = node6;

    Solution solution = new Solution();
    TreeNode node = solution.deleteNode(node5, 3);

    System.out.println(node);
  }

  static
  class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
      if (root == null) {
        return root;
      }
      if (root.val == key) {
        if (root.left == null && root.right == null) {
          return null;
        }
        if (root.left == null || root.right == null) {
          return root.left != null ? root.left : root.right;
        }
        TreeNode father = root;
        TreeNode candidate = root.right;
        while (candidate.left != null) {
          father = candidate;
          candidate = candidate.left;
        }
        if (candidate == root.right) {
          candidate.left = root.left;
          return candidate;
        }
        father.left = candidate.right;
        candidate.left = root.left;
        candidate.right = root.right;
        return candidate;
      }
      if (key < root.val) {
        root.left = deleteNode(root.left, key);
      } else {
        root.right = deleteNode(root.right, key);
      }
      return root;
    }

  }

}
